import sys
sys.setrecursionlimit(100000000)  #手动让他最大深度变大
d2=[1,3]
d3=[2,0]
d4=[3,0]
lst=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
def lst_to_matrix(width, lst):  #注意，生成的是横优先的，也就是先从左往右再从上到下的，这样与image模块的采样顺序一致
    newlst=[]
    templst=[]
    height=int(len(lst) / width)
    begin=0
    end=width
    for _ in range(height):
        newlst.append(lst[begin:end])
        begin+=width
        end+=width
    # print(newlst)
    return newlst
def make_matrix(matrix_width, lst):   #生成矩阵
    templst = []
    newlst = []
    for i in range(matrix_width * matrix_width):
        templst.append(0)
    newlst=lst_to_matrix(matrix_width, templst)

    for d in lst:
        # print(d)
        newlst[d[0]][d[1]]=1
    for row in newlst:
        print(row)
def on_colomn(lst):  #判断是不是同一列
    newlst=[]
    # print(lst)
    for _ in lst:
        newlst.append(_[1])

    set1=set(newlst)
    lst1=list(set1)
    # print(len(lst))
    # print(len(lst1))
    if len(newlst)==len(lst1):
        #print(1)
        return 1
    else:
        #print(0)
        return 0
def on_diagonal(lst):     #对角线判断，判断两个点是否在对角线上
    # print(lst)
    for i in lst:
        for j in lst:
            # print(i,j)
            if i!=j and abs(i[0]-j[0])==abs(i[1]-j[1]):
                # print(i,j,"在一个对角线上")
                return 0
            else:
                pass
                # print(i,j,"不在一个对角线上")
    return 1
exisited=[]
global T
T=0

def N_Queen(point, enabledown, N):
    global T
    unable_sign=0
    down=0
    right=0
    up=0
    exisited.append(point)
    if point[0]==0 and point[1]==N-1 and enabledown==0:    #标志递归结束
        return
    if point[0]==N-1:
        enabledown=0          #不能让他再下走
    # print(已存在点栈)
    if on_colomn(exisited) and on_diagonal(exisited) and point[0]==N-1:
        print(f'找到第{T+1}种结果')
        make_matrix(N, exisited)
        # print('\n')
        T+=1
    if on_colomn(exisited) and on_diagonal(exisited) and enabledown:   #这是找到符合条件的
        # print(point,'此点可以,往下走')
        down=1
    else:
        unable_sign=1
    if unable_sign==1 and point[1]!=N-1:
        # print(point,'此点不行,继续右走')
        exisited.pop()
        right=1
    if unable_sign==1 and point[1]==N-1:
        # print(point,'此行不行，往回走')
        exisited.pop()
        up=1


    if down==1 and enabledown:
        newpoint=[point[0]+1,0]
        N_Queen(newpoint, 1, N)
    if right==1:
        newpoint=[point[0],point[1]+1]
        N_Queen(newpoint, 1, N)
    if up==1:
        point=exisited[-1]
        # print('回到了',point)
        exisited.pop()
        newpoint=[point[0],point[1]]
        N_Queen(newpoint, 0, N)

N=8          #这个就是多少皇后，把这个改成9就是9皇后问题
print(N,"皇后问题：")
on_diagonal(exisited)
on_colomn(exisited)
d1=[0,0]                   #初始化

N_Queen(d1, 1, N)    #开始回溯
print(f'一共有',T,'种')
# 生成矩阵(4,已存在点栈)